{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This question asks to prove that maxmizing variance with the first principal component from PCA is equivalent to minimize the mean squared error (MSE)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a unit vector $u$, the projection of $x$ onto it is \n",
    "\n",
    "$$\n",
    "f_u(x) = (u^T x) u\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then,\n",
    "\n",
    "\\begin{align*}\n",
    "\\mathrm{MSE}\n",
    "&= \\frac{1}{m} \\sum_{i=1}^m \\left \\| x^{(i)} - f_u(x^{(i)}) \\right \\|_2^2 \\\\\n",
    "&= \\frac{1}{m} \\sum_{i=1}^m \\bigg( \\big(x^{(i)} - (u^T x^{(i)})u \\big)^T \\big(x^{(i)} - (u^T x^{(i)})u \\big) \\bigg )\\\\\n",
    "&= \\frac{1}{m} \\sum_{i=1}^m  \\bigg( (x^{(i)})^Tx^{(i)} - \\big( (u^T x^{(i)})u \\big)^T x^{(i)} - (x^{(i)})^T\\big( (u^T x^{(i)})u \\big) + \\big( (u^T x^{(i)})u \\big)^T \\big( (u^T x^{(i)})u \\big) \\bigg ) \\\\\n",
    "&= \\frac{1}{m} \\sum_{i=1}^m \\bigg( (x^{(i)})^Tx^{(i)} - 2 (u^T x^{(i)}) (u ^T x^{(i)}) + (u^T x^{(i)})^2 (u^Tu) \\bigg ) \\\\\n",
    "&= \\frac{1}{m} \\sum_{i=1}^m \\bigg( (x^{(i)})^Tx^{(i)} - (u^T x^{(i)})^2 \\bigg ) \\\\\n",
    "&= \\frac{1}{m} \\sum_{i=1}^m (x^{(i)})^Tx^{(i)} - \\frac{1}{m} \\sum_{i=1}^m (u^T x^{(i)})^2 \\\\\n",
    "&= \\frac{1}{m} \\sum_{i=1}^m (x^{(i)})^Tx^{(i)} - \\bigg( \\frac{1}{m} \\sum_{i=1}^m u^T x^{(i)} \\bigg)^2 - \\mathrm{Var}(u^Tx^{(i)})\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compared to the equation in the problem set, I added $\\frac{1}{m}$ to the MSE, which won't affect the minization/maximization problem.\n",
    "\n",
    "The last equality uses the fact about variance and mean that is $E[(X - \\bar X)^2] = (E[X])^2 - E[(X^2)]$.\n",
    "\n",
    "This proves that maximizing the variance is equivalent to minimizing the MSE."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
